home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.cs.arizona.edu
/
ftp.cs.arizona.edu.tar
/
ftp.cs.arizona.edu
/
icon
/
newsgrp
/
group98a.txt
/
000128_icon-group-sender _Fri Mar 13 08:07:45 1998.msg
< prev
next >
Wrap
Internet Message Format
|
2000-09-20
|
3KB
Return-Path: <icon-group-sender>
Received: from kingfisher.CS.Arizona.EDU (kingfisher.CS.Arizona.EDU [192.12.69.239])
by baskerville.CS.Arizona.EDU (8.8.7/8.8.7) with SMTP id IAA23735
for <icon-group-addresses@baskerville.CS.Arizona.EDU>; Fri, 13 Mar 1998 08:07:44 -0700 (MST)
Received: by kingfisher.CS.Arizona.EDU (5.65v4.0/1.1.8.2/08Nov94-0446PM)
id AA17073; Fri, 13 Mar 1998 08:07:44 -0700
Message-Id: <35089F74.6018@gte.net>
Date: Thu, 12 Mar 1998 20:52:36 -0600
From: Mark Evans <evans@gte.net>
Reply-To: evans@gte.net
Organization: None
X-Mailer: Mozilla 3.01 (Win95; I)
Mime-Version: 1.0
To: icon-group@optima.CS.Arizona.EDU
Cc: evans@gte.net
Subject: Letter Probabilities
References: <Pine.SOL.3.96.980312052940.7871A-100000@post.its.mcw.edu> <350813B6.503F@gte.net> <35089EC7.49D@gte.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Errors-To: icon-group-errors@optima.CS.Arizona.EDU
Status: RO
Content-Length: 1743
Here is a small Icon problem related to letter probabilites. Each
letter has a "probability of occurrence" in the information-theoretic
setting. This probability can be estimated from sample texts. I want
to generate random text based on these probabilities.
I have a table that associates inidividual letters (one-char strings)
with real numbers (probabilities). We can assume for the sake of
argument that the sum of all probabilities in my table is unity.
Given this table (which I already have Icon code to obtain) what is the
most efficient method of generating random text? What I am thinking of
at the moment is:
(1) get a sorted list of [key,value] pairs,
sorted by value (probability),
highest probability first
(2) generate a random number from 0.0 to 1.0
(3) use a while-loop to find the slot in the
sorted list where the number falls;
I would subtract each passing probability
until my placeholder value had vanished; e.g.
i := 0 # running index
x := ?0 # random number 0.0 - 1.0
while x > 0 do
{
i +:= 1
x -:= prob_list[i][2]
}
letter := prob_list[i][1]
This all seems rather awkward to me, especially step (3). Isn't there
some construct in Icon that could do this more elegantly? Some way to
search a list for a pair of elements that bracket a variable value?
Mark
P.S. I am already very well acquainted with the sample program
'monkeys.icn' in the distribution. This program uses multiple-character
sequences, not individual letter probabilities. More characters gives a
better approximation to the source language, but I am interested
specifically in single-character probabilities right at the moment.